#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode
{
  int val;
  struct TreeNode* left;
  struct TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
  // 全局变量
 private:
  TreeNode* pre;

 public:
  TreeNode* Convert(TreeNode* pRootOfTree)
  {
    // 根节点要有效
    if (nullptr == pRootOfTree) return nullptr;

    pre = nullptr;  // 初始化成员变量，用于记录上一次访问的结点

    convertNode(pRootOfTree);

    TreeNode* head = pRootOfTree;

    while (head->left) head = head->left;  // 二叉搜索树中最左子结点即为中序遍历的第一个结点

    return head;
  }

 private:
  void convertNode(TreeNode* cur)
  {
    if (nullptr == cur) return;  // 递归的出口一
    cout << "12" << endl;
    // 转换左子树
    convertNode(cur->left);

    // 根据递归的debug得知，先在转换左子树函数中递归处理完所有的左子树节点：处理指的是添加节点间的指针
    // 然后调用转换根节点，再转换右子树
    // 递归就是分封制，左子树也相当于一棵完整树里面也分为左子树，根节点，右子树，分别递归调用相应的函数
    // 因此假定只有一颗最基本的树，只要这些操作对这棵树能满足，再大的树也能满足

    // 转换根节点
    cur->left = pre;
    if (pre) pre->right = cur;
    pre = cur;  // 记录被处理过的节点

    // 转换右子树
    convertNode(cur->right);
  }
};

int main()
{
  TreeNode* pA = new TreeNode(5);
  TreeNode* pB = new TreeNode(3);
  TreeNode* pC = new TreeNode(8);

  pA->left = pB;
  pA->right = pC;

  Solution solute;
  solute.Convert(pA);
}

/*
排序列表就是二叉搜索树的中序遍历
方法一：中序遍历迭代法
参考题目： Validate Binary Search Tree）


class Solution
{
 public:
  TreeNode* Convert(TreeNode* root)
  {
    if (nullptr == root) return nullptr;
    // 保证根节点是有效节点
    TreeNode* head = root;
    while (head->left) head = head->left;  // 二叉搜索树中最左子结点即为中序遍历的第一个结点

    stack<TreeNode*> s;
    TreeNode *p = root, *pre = nullptr;

    while (p || !s.empty())  // p有效，s不为空
    {
      if (p)
      {
        s.push(p);
        p = p->left;
      }
      else  // p已经是最左侧叶子节点
      {
        p = s.top();
        p->left = pre;            // 连接p与pre(头节点)
        if (pre) pre->right = p;  // 连接pre与p
        pre = p;                  // 更新pre
        s.pop();

        p = p->right;
      }
    }
    return head;
  }
};
*/
